/*
 * @lc app=leetcode.cn id=703 lang=cpp
 *
 * [703] 数据流中的第 K 大元素
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class KthLargest
{
    priority_queue<int, vector<int>, greater<int>> lessq;
    priority_queue<int> bigq;
    int k;

public:
    KthLargest(int k, vector<int> &nums)
    {
        this->k = k;
        std::sort(nums.begin(), nums.end(), [](int l, int r) -> bool
                  { return l > r; });

        const int m = nums.size() > k ? k : nums.size();
        for (int i = 0; i < m; i++)
        {
            lessq.push(nums[i]);
        }
        for (size_t i = k; i < nums.size(); i++)
        {
            bigq.push(nums[i]);
        }
    }

    int add(int val)
    {
        if (lessq.size() < k)
        {
            lessq.push(val);
            return lessq.top();
        }

        int kth = lessq.top();
        if (val <= kth)
            bigq.push(val);
        else
        {
            lessq.pop();
            bigq.push(kth);
            lessq.push(val);
            kth = lessq.top();
        }
        return kth;
    }
};

// int main(int argc, char const *argv[])
// {
//     auto v = vector<int>({4,5,8,2});
//     KthLargest a(3, v);
//     a.add(3);
//     a.add(5);
//     a.add(10);
//     a.add(9);
//     a.add(4);
//     return 0;
// }


/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */
// @lc code=end
